using System;
using System.Runtime.CompilerServices;

namespace HTCollections.Unsafe
{
    public static class UnsafeCollectionsExtension
    {
        /// <summary>
        /// 冒泡排序（复杂度O(n^2), 稳定）
        /// </summary>
        /// <param name="array">Unsafe 数组</param>
        /// <param name="comparer">比较器(return a1>a2 : 升序)</param>
        /// <typeparam name="T">非托管类型</typeparam>
        public static unsafe void Sort_Bubble<T>(this UnsafeArray<T> array, Func<T, T, bool> comparer)
            where T : unmanaged
        {
            var arrayPtr = array.Ptr;
            int length = array.Length;
            for (int i = 1; i < length; i++)
            {
                for (int j = 0; j < length - i; j++)
                {
                    T a = arrayPtr[j];
                    T b = arrayPtr[j + 1];
                    if (comparer(a, b))
                    {
                        arrayPtr[j] = b;
                        arrayPtr[j + 1] = a;
                    }
                }
            }
        }

        /// <summary>
        /// 冒泡排序（复杂度O(n^2), 稳定）
        /// </summary>
        /// <param name="list">Unsafe 列表</param>
        /// <param name="comparer">比较器(return a1>a2 : 升序)</param>
        /// <typeparam name="T">非托管类型</typeparam>
        public static unsafe void Sort_Bubble<T>(this UnsafeList<T> list, Func<T, T, bool> comparer)
            where T : unmanaged, IEquatable<T>
        {
            var arrayPtr = list.Ptr;
            int length = list.Length;
            for (int i = 1; i < length; i++)
            {
                for (int j = 0; j < length - i; j++)
                {
                    T a = arrayPtr[j];
                    T b = arrayPtr[j + 1];
                    if (comparer(a, b))
                    {
                        arrayPtr[j] = b;
                        arrayPtr[j + 1] = a;
                    }
                }
            }
        }

        /// <summary>
        /// 快速排序（复杂度O(log n), 不稳定）
        /// </summary>
        /// <param name="array">Unsafe 数组</param>
        /// <param name="comparer">比较器(return a1>a2 : 升序)</param>
        /// <typeparam name="T">非托管类型</typeparam>
        public static unsafe void Sort_Quick<T>(this UnsafeArray<T> array, Func<T, T, bool> comparer)
            where T : unmanaged
        {
            var arrayPtr = array.Ptr;
            int length = array.Length;
            Sort_Quick(arrayPtr, 0, length - 1, comparer);
        }

        /// <summary>
        /// 快速排序（复杂度O(log n), 不稳定）
        /// </summary>
        /// <param name="list">Unsafe 列表</param>
        /// <param name="comparer">比较器(return a1>a2 : 升序)</param>
        /// <typeparam name="T">非托管类型</typeparam>
        public static unsafe void Sort_Quick<T>(this UnsafeList<T> list, Func<T, T, bool> comparer)
            where T : unmanaged, IEquatable<T>
        {
            var arrayPtr = list.Ptr;
            int length = list.Length;
            Sort_Quick(arrayPtr, 0, length - 1, comparer);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe void Sort_Quick<T>(T* array, int left, int right, Func<T, T, bool> comparer) where T : unmanaged
        {
            if (left >= right) return;
            int key = Partition_Quick(array, left, right, comparer);
            Sort_Quick(array, left, key - 1, comparer);
            Sort_Quick(array, key + 1, right, comparer);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe int Partition_Quick<T>(T* array, int left, int right, Func<T, T, bool> comparer)
            where T : unmanaged
        {
            // int midIndex = GetMidIndex_Quick(array, left, right, comparer);
            // Swap(&array[left], &array[midIndex]);
            int key = left;
            while (left < right)
            {
                while (left < right && !comparer.Invoke(array[key], array[right]))
                    right--;
                while (left < right && !comparer.Invoke(array[left], array[key]))
                    left++;
                Swap(&array[left], &array[right]);
            }

            Swap(&array[left], &array[key]);
            return left;
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe int GetMidIndex_Quick<T>(T* array, int left, int right, Func<T, T, bool> comparer)
            where T : unmanaged
        {
            int mid = (left + right) >> 1;
            if (comparer.Invoke(array[right], array[mid]))
            {
                if (comparer.Invoke(array[mid], array[left]))
                    return mid;
                else if (comparer.Invoke(array[right], array[left]))
                    return left;
                else
                    return right;
            }
            else
            {
                if (comparer.Invoke(array[left], array[mid]))
                    return mid;
                else if (comparer.Invoke(array[left], array[right]))
                    return left;
                else
                    return right;
            }
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static unsafe void Swap<T>(T* left, T* right) where T : unmanaged
        {
            T temp = *left;
            *left = *right;
            *right = temp;
        }
    }
}